public class MaxPathSum {
    private static int maxSum = -0x3f3f3f3f;
    public int maxPathSum (TreeNode root) {
        // write code here
        dfs(root);
        return maxSum;
    }

    // 返回当前节点的最大贡献值
    private int dfs(TreeNode root) {
        if(root == null) return 0;

        int leftSum = Math.max(dfs(root.left), 0);
        int rightSum = Math.max(dfs(root.right), 0);
        // leftSum+rightSum+root.val记录经过当前节点的路径和
        maxSum = Math.max(maxSum, leftSum+rightSum+root.val);
        // 返回当前节点的最大贡献值
        return root.val + Math.max(leftSum, rightSum);
    }
}
